<?php
// Author :　evilair
// Time : 2017/08/07

/***************************************
* 装水最多的容器
* 给定n个正整数,对应n组数值(i, ai), i对应为x轴坐标,ai对应y轴坐标,
* 加上x轴,找最大的体积
* 每组数对应一个线段,线段的两点坐标为(i,ai),(i,0)
*
****************************************/
function getMaxArea($high)
{
  $maxArea = 0;
  $outFor = 1;
  foreach ($high as $outkey => $outvalue) {
    # 第一次循环
    $outFor++;
    # 初始化第二次循环的次数
    $inFor = 1;
    foreach ($high as $key => $value) {
      # 二次循环的开始位置
      if ($inFor <= $outFor) {
        $inFor++;
        continue;
      } 
      # 二次循环
      $maxArea = $maxArea > getArea($high, $outkey, $key) ? $maxArea : getArea($high, $outkey, $key);
    }
  }
  return $maxArea;
}

function getArea($high, $x1, $x2)
{
  $minHigh = $high[$x1] < $high[$x2] ? $high[$x1] : $high[$x2];
  return ($x2-$x1)*$minHigh;
}
$high = [
  3 => 100,
  8 => 52,
  12 => 99
];
// echo getMaxArea($high);
// echo getArea($high, 3, 12);

// 只能是索引数组了
function maxArea($arr)
{
  $maxArea = 0;
  $left = 0;
  $right = count($arr) - 1;
  if ($right <= 0) {
    return '数组长度太小了';
  }
  while ($left < $right) {
    $tempArea = ($right - $left) * ($arr[$right] > $arr[$left] ? $arr[$left] : $arr[$right]);
    $maxArea = $maxArea > $tempArea ? $maxArea : $tempArea;

    if ($arr[$left] < $arr[$right]) {
      do {
        $left++;
      } while($left < $right && $arr[$left-1] >= $arr[$left] );
    } else {
      do {
        $right--;
      } while($right > $left && $arr[$right] <= $arr[$right+1]);
    }
  }
  return $maxArea;
}

$teatArr = [5, 9, 2, 12, 6, 8, 45, 32, 10];
echo maxArea($teatArr);
echo "\n";
echo getMaxArea($teatArr);
